package com.mingqi.hw.test1120;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 单词接龙的规则是：可用于接龙的单词首字母必须要前一个单词的尾字母相同；当存在多个首字母相同的单词时，取长度最长的单词，如果长度也相等，则取字典序最小的单词；已经参与接龙的单词不能重复使用。
 * 现给定一组全部由小写字母组成单词数组，并指定其中的一个单词作为起始单词，进行单词接龙，请输出最长的单词串，单词串是单词拼接而成，中间没有空格。
 * 输入描述:
 * 输入的第一行为一个非负整数，表示起始单词在数组中的索引K，0 <= K < N ；
 * 输入的第二行为一个非负整数，表示单词的个数N；
 * 接下来的N行，分别表示单词数组中的单词。
 * 输出描述:
 * 输出一个字符串，表示最终拼接的单词串。
 * 示例1：
 * 输入
 * 0
 * 6
 * word
 * dd
 * da
 * dc
 * dword
 * d
 * 输出
 * worddwordda
 * 说明
 * 先确定起始单词word，再接以d开头的且长度最长的单词dword，剩余以d开头且长度最长的有dd、da、dc，则取字典序最小的da，所以最后输出worddwordda。
 * 示例2：
 * 输入
 * 4
 * 6
 * word
 * dd
 * da
 * dc
 * dword
 * d
 * 输出
 * dwordda
 * 说明
 * 先确定起始单词dword，剩余以d开头且长度最长的有dd、da、dc，则取字典序最小的da，所以最后输出dwordda。
 * 备注:
 * 单词个数N的取值范围为[1, 20]；
 * 单个单词的长度的取值范围为[1, 30]；
 */
public class ZT12 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        while (scanner.hasNext()){
            int startIndex=scanner.nextInt(); //起始单词在数组中的索引
            int count=scanner.nextInt();//单子的个数
            String [] words=new String[count];
            String startWords="";
            for(int i=0;i<count;i++){
                words[i]=scanner.next();
                if(startIndex==i){
                    startWords=words[i];
                }
               // System.out.println(words[i]);
            }
            String longestChain = buildLongestChain(words, startWords);

            System.out.println(longestChain);
        }
    }
    private static String buildLongestChain(String[] words, String currentWord) {
        if (currentWord == null) return "";

        // 查找下一个符合条件的单词
        String  nextWord= findNextWord(words, currentWord);

        if (nextWord == null) return currentWord; // 没有下一个单词，结束

        // 递归构建剩余的单词链，并移除已使用的单词
        String remainingChain = buildLongestChain(Arrays.stream(words).filter(word -> !word.equals(nextWord)).toArray(String[]::new), nextWord);
        //String remainingChain = buildLongestChain(words, nextWord);
        return currentWord + remainingChain;
    }

    private static String findNextWord(String[] words, String currentWord) {
        char endChar = currentWord.charAt(currentWord.length() - 1);
        return Arrays.stream(words)
                .filter(word -> word.charAt(0) == endChar && !word.equals(currentWord))
                .max((w1, w2) -> {
                    if (w1.length() != w2.length()) return w1.length() - w2.length(); // 长度优先
                    else return w2.compareTo(w1); // 字典序
                })
                .orElse(null);
    }
}
